/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package huffmancompression;

import java.util.LinkedList;

/**
 *
 * @author Agustin
 */
public class QuickSort {
    
    public QuickSort(){
    }
    
    public LinkedList<Integer> Sort(LinkedList<Integer> arreglo, LinkedList<String> C){
        LinkedList<Integer> A = arreglo;
        
        this.QuickSortMethod(A, 0, A.size() - 1, C);
        
        return A;
    }
    
    private void QuickSortMethod(LinkedList<Integer> A, int p, int r, LinkedList<String> C){
        int q = 0;
        if(p < r){
            q = this.Partition(A, p, r, C);
            this.QuickSortMethod(A, p, q -1, C);
            this.QuickSortMethod(A, q + 1, r, C);
        }
    }
    
    private int Partition(LinkedList<Integer> A, int p, int r, LinkedList<String> C){
        int x = A.get(r);
        String s = "";
        int i = p - 1;
        int temp = 0;
        
        for(int j = p; j < r; j++){
            if(A.get(j) <= x){
                i++;
                temp = A.get(j);
                A.set(j, A.get(i));
                A.set(i, temp);
                
                s = C.get(j);
                C.set(j, C.get(i));
                C.set(i, s);
            }
        }
        temp = A.get(r);
        A.set(r, A.get(i + 1));
        A.set(i + 1, temp);
        
        s = C.get(r);
        C.set(r, C.get(i + 1));
        C.set(i + 1, s);
        
        return i + 1;
    }
}
